using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Solver
{
	/// <summary>
	/// Non-negative decimal integer number
	/// </summary>
	internal class Number
	{
		//least significant digits go first
		private byte[] digits_;

		#region ctor

		private Number(byte[] digits)
		{
			digits_ = digits;
		}

		public Number(string n)
		{
			digits_ = n.Trim().Replace("-", string.Empty).ToCharArray().Reverse().Select(c => (byte)(c - '0')).ToArray();
		}

		public Number(Int32 n)
			: this((Int64)n)
		{ }

		public Number(Int64 n)
		{
			if (n < 0)
				throw new ArgumentException("Only non-negative numbers are supported.");
			CtorInternal((UInt64)n);
		}

		public Number(UInt32 n)
			: this((UInt64)n)
		{ }

		public Number(UInt64 n)
		{
			CtorInternal(n);
		}

		private void CtorInternal(UInt64 n)
		{
			var log10 = Math.Log10(n);
			var length = log10 > 0 ? Convert.ToInt32(Math.Floor(log10)) : 0;
			digits_ = new byte[length + 1];
			int i = 0;
			do
			{
				digits_[i++] = (byte)(n % 10);
				n /= 10;
			} while (n != 0);
		}

		#endregion

		#region conversion

		public override string ToString()
		{
			var sb = new StringBuilder(digits_.Length);
			sb.Append(digits_.Reverse().Select(d => (char)(d + '0')).ToArray());
			return sb.ToString();
		}

		public Int32 ToInt32()
		{
			return Int32.Parse(ToString());
		}

		public Int64 ToInt64()
		{
			return Int64.Parse(ToString());
		}

		public UInt32 ToUInt32()
		{
			return UInt32.Parse(ToString());
		}

		public UInt64 ToUInt64()
		{
			return UInt64.Parse(ToString());
		}

		#endregion

		public Number Clone()
		{
			return new Number((byte[])digits_.Clone());
		}

		public int Length
		{
			get { return digits_.Length; }
		}

		public IEnumerable<int> Digits()
		{
			foreach (var d in digits_)
				yield return d;
		}

		public Number Add(Number rhs)
		{
			var maxLen = digits_.Length;
			if (maxLen < rhs.digits_.Length) maxLen = rhs.digits_.Length;
			var resultDigits = new byte[maxLen];
			byte toRemember = 0;
			for (int index = 0; index < maxLen; index++)
			{
				int s = ExtractDigit(digits_, index) + ExtractDigit(rhs.digits_, index) + toRemember;
				if (s <= 9)
				{
					resultDigits[index] = (byte)s;
					toRemember = 0;
				}
				else
				{
					resultDigits[index] = (byte)(s - 10);
					toRemember = 1;
				}
			}
			if (toRemember != 0)
			{
				Array.Resize(ref resultDigits, maxLen + 1);
				resultDigits[maxLen] = 1;
			}
			return new Number(resultDigits);
		}

		private static byte ExtractDigit(byte[] digits, int index)
		{
			return index < digits.Length ? digits[index] : (byte)0;
		}

		public Number Multiply(Number rhs)
		{
			var result = new Number(0);
			for (int i = 0; i < rhs.digits_.Length; i++)
			{
				byte toRemember = 0;
				var tempDigits = new byte[digits_.Length + i];
				for (int j = 0; j < digits_.Length; j++)
				{
					var t = rhs.digits_[i] * digits_[j] + toRemember;
					tempDigits[j + i] = (byte)(t % 10);
					toRemember = (byte)(t / 10);
				}
				if (toRemember != 0)
				{
					Array.Resize(ref tempDigits, tempDigits.Length + 1);
					tempDigits[tempDigits.Length - 1] = toRemember;
				}
				result = result.Add(new Number(tempDigits));
			}
			return result;
		}
	}
}